Computer graphics employ a number of techniques to reproduce curved lines and surfaces. One commonly used technique involves producing a set of points and connecting those points with straight lines to approximate the curve. The curve is successively divided into smaller pieces and then checked to see if each piece can be approximated by a straight line to within a given error threshold. It turns out that the check of the accuracy of the approximation is the dominant part of the cost of executing the curve approximation algorithm.
In a two-dimensional space, a curve is often expressed as a function of orthogonal components x and y, i.e., y is equal to f(x). In a three-dimensional coordinate system, the x, y and z coordinates may also be represented as functions of one or two of the orthogonal components. However, these representations may cause difficulty in generating the coordinate values. One alternative technique is to use a parametric representation of the curve or a representation where each coordinate value on a curve is represented as a function of some common variable, that is, a variable common to all coordinate components. For a three dimensional system, such a variable may be described as t resulting in the following: x=f(t); y=g(t); and z=h(t); for 0&lt;t&lt;1. A further representation is a parametric cubic curve that is represented by third order polynomials. EQU x=f(t)=a.sub.x t.sup.3 +b.sub.x t.sup.2 +c.sub.x t+d.sub.x EQU y=g(t)=a.sub.y t.sup.3 +b.sub.y t.sup.2 +c.sub.y t+d.sub.y EQU z=h(t)=a.sub.x t.sup.3 +b.sub.y t.sup.2 +c.sub.z t+d.sub.z
Cubic curves are important because no lower-order representation of curve segments can provide either continuity of position and slope or continuity of slope and curvature at the point where the curve segments meet. Cubic curves are also the lowest order curves that can render non-planar curves in three dimensions.
A popular prior art method for subdividing parametric cubic curves is termed "Bezier subdivision". The Bezier subdivision method will be briefly described, but no explanation or proof of its correctness will be given. Such proofs may be found in various texts on graphics, i.e., see "Fundamentals of Interactive Computer Graphic, Foley et al., Addison-Wesley Publishing Co., pp. 514-523; "Algorithms for Graphics and Image Processing", Pavlidis, Computer Science Press, pp. 220-231; and "Computational Geometry For Design and Manufacture", Faux et al., Wiley and Sons, pp. 126-145.
Given a curve and an error threshold .DELTA..sub.E, the Bezier algorithm produces a list of line segments which approximate the curve with errors no larger than .DELTA..sub.E. The curve itself is described by a control polygon consisting of 4 points, p1, p2, p3, p4. Such a control polygon is shown in FIG. 1 and which also includes cubic curve 10 is being approximated. The dimension E is the error and defines the distance between the chord p1-p4 and the apogee of curve 10. If E is greater than .DELTA..sub.E two more polygons are constructed from the original polygon, with the property that curve 10 lies within each new polygon, and that each new polygon is the control polygon for the part of the curve which it contains. This subdivision proceeds recursively.
An iteration of this subdivision process has three stages. The first stage is indicated in FIG. 2 wherein the following values are found: ##EQU1##
The second stage of the calculation is shown in FIG. 3 and shows the derivation of points 13 and r2 as follows: ##EQU2##
The third stage involves the derivation of points l4 and r1 as follows: ##EQU3##
At the end of the above iterations, the derived values are: ##EQU4##
As can be seen from FIG. 4, the Bezier control polygons l1-l4 and r1-r4 now better approximate curve 10. For any given resolution .DELTA..sub.E, the subdivision process ends when, any curve within a polygon is at most a distance .DELTA..sub.E from the base line of that polygon. (The base line of the polygon is the line connecting P1 to P4). The calculation may be simplified by calculating the value for d instead of .DELTA..sub.E (see FIG. 1).
In essence, Bezier subdivision generates a binary tree where each node of the tree corresponds to a subdivision step, and each edge of the tree descending from a node corresponds to a right or left control polygon that is the result of a subdivision at that node. In a simple implementation, the calculation cost for each node includes approximately 12 additions and 12 shifts (24 cycles). However, the error check for .DELTA..sub.E requires at least 350 additional cycles. Thus, most of the computational work (88%) is in computing the error condition .DELTA..sub.E at the end of each iteration. Similar disparities in calculation work exist for more complex equations, i.e., parametric quadratics, conics, etc.